package dfs;


import java.util.Arrays;


//TODO:2023/9/17   统计所有可行的路劲  燃油  https://blog.csdn.net/YMY6666/article/details/108465638?spm=1001.2101.3001.6650.6&utm_medium=distribute.pc_relevant.none-task-blog-2%7Edefault%7EBlogCommendFromBaidu%7ERate-6-108465638-blog-119935401.235%5Ev38%5Epc_relevant_sort_base3&depth_1-utm_source=distribute.pc_relevant.none-task-blog-2%7Edefault%7EBlogCommendFromBaidu%7ERate-6-108465638-blog-119935401.235%5Ev38%5Epc_relevant_sort_base3&utm_relevant_index=5
public class Class1575 {

    //TODO:2023/9/17   最初
    int num = 0;
    public int countRoutes2(int[] locations, int start, int finish, int fuel) {
        //从开始城市进行搜索
        dfs1(locations, start, finish, fuel);
        return num;
    }

    public void dfs1(int[] locations, int start, int finish, int fuel){
        //到达目的地且油量>=0时，路径总数+1
        if(start == finish && fuel>=0){
            num = num+1>1000000007?(num+1)%1000000007:num+1;
        }
        //搜索可到达的下一个城市
        for(int i = 0;i<locations.length;i++){
            //到达下一个城市还剩的油量
            int k = fuel-Math.abs(locations[start] - locations[i]);
            //如果下一个城市和就是当前城市或者油量不足，则不去，直接查询下一个城市
            if(i == start || k<0){
                continue;
            }
            //搜索下一个可达城市
            dfs1(locations, i, finish, k);
        }
    }

//TODO:2023/9/17  改进一

    //map[i][j]记录从i到j需要消耗的油量
    int[][] map;
    //k=dp[start][fuel] 拥有fuel单位的油从start城市到达目的地，共有temp条路径,
    int dp[][];
    public int countRoutes3(int[] locations, int start, int finish, int fuel) {
        int len = locations.length;
        map = new int[len][len];
        //初始化map
        for (int i = 0; i < len; i++) {
            for (int j = i+1; j < len; j++) {
                int num = Math.abs(locations[i] - locations[j]);
                map[i][j] = num;
                map[j][i] = num;
            }
        }
        dp = new int[len][fuel + 1];
        //初始化dp
        for (int[] temp : dp) {
            Arrays.fill(temp, -1);
        }
        //开始深搜
        return dfs(start, finish, fuel);
    }

    private int dfs(int start, int finish, int fuel) {
        //判断在start城市拥有fuel的油量是否已经搜索过，没有搜索过才进行搜索,如果搜索过直接返回
        if (dp[start][fuel] == -1) {
            //判断是否到达目的地，到达则路径数为1,没到达则为0
            int temp = start == finish ? 1 : 0;
            for (int i = 0; i < map.length; i++) {
                //搜索拥有fuel油量可到达的非当前城市
                if (i != start && map[start][i] <= fuel) {
                    //继续从当前城市开始搜索,累加路径数
                    temp += dfs(i, finish, fuel - map[start][i]);
                    temp %= 1000000007;
                }
            }
            //拥有fuel单位的油从start城市到达目的地，共有temp条路径,
            dp[start][fuel] = temp;
        }
        return dp[start][fuel];
    }





    //TODO:2023/9/17 下面是我自己默写的

    int ans=0;
    public int countRoutes(int[] locations, int start, int finish, int fuel) {
         dfs(locations, start, finish, fuel);
         return  ans;
    }

    public  void  dfs(int[] locations,int start,int finish,int fuel){

   if (start==finish&&fuel>=0){
       ans=(ans+1)>1000000007?(ans+1)%1000000007:(ans+1);
       return;
   }
        for (int i = 0; i < locations.length; i++) {
            int k=fuel-Math.abs(locations[start]-locations[i]);
            if(i == start || k<0){
                continue;
            }
            //搜索下一个可达城市
            dfs(locations, i, finish, k);
        }

    }

    public static void main(String[] args) {
        Class1575 class1575 = new Class1575();
        int[] loc={4,3,1};
        int i = class1575.countRoutes(loc, 1, 0, 6);
        System.out.println(i);


    }
}
